package chapter02;


public class ReverseBetween92 {
    /**
     * 建立一个头节点headNode便于操作链表
     * count记录链表节点位置 初始化count==1
     * 将链表分为三部分 第一部分的最后一个节点preNode 中间部分的头midHead和尾midTail 后面部分的头tailNode
     * 循环查找节点并记录count
     *  1).如果count第一次位于[left,right] 循环更新count并记录preNode midHead midTail tailNode
     *      直到count出界或者循环节点为空
     *      利用头插法将位于中间部分的节点逆转
     *      完成后将preNode与midTail相连 midHead和tailNode相连
     *      直接退出循环
     *  2).否则将循环节点直接连接到第一部分上 更新count
     * 返回第一部分的头节点 headNode.next
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode headNode=new ListNode();
        ListNode preNode=headNode,midHead=null,midTail=null,tailNode=null;
        int count=1;
        while (head!=null){
            if(count>=left&&count<=right){
                midHead=head;
                while (head!=null&&count>=left&&count<=right){
                    count++;
                    midTail=head;
                    head=head.next;
                }
                tailNode=head;
                reverse(midHead,midTail);
                preNode.next=midTail;
                midHead.next=tailNode;
                break;
            }else{
                count++;
                preNode.next=head;
                preNode=head;
                head=head.next;
            }
        }
        return headNode.next;
    }

    public void reverse(ListNode head, ListNode tail){
        ListNode headNode=new ListNode();
        headNode.next=null;
        ListNode p=head;
        while (p!=tail){
            ListNode q=p;
            p=p.next;
            q.next=headNode.next;
            headNode.next=q;
        }
        p.next=headNode.next;
        headNode.next=p;
    }
}
